#define  _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> ret;
    string path, s;
    vector<bool> vis;
    size_t len;
    vector<string> permutation(string _S) {
        sort(_S.begin(), _S.end());
        s = _S;
        vis.resize(_S.size(), false);
        len = _S.size();
        dfs();
        return ret;
    }
    void dfs()
    {
        if(path.size() == s.size())
        {
            ret.push_back(path);
            return;
        }
        for (size_t i = 0; i < len; i++)
        {
            if (vis[i]) continue;
            if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;

            vis[i] = true;
            path.push_back(s[i]);
            dfs();
            vis[i] = false;
            path.pop_back();
        }
    }
};